Forum:ITTM cryptography
Call a function \(F: \mathbb{R}^i \mapsto \mathbb{R}^j\) ITTM-computable iff there is an ITTM \(T\) such that, for every \(i\)-tuple of reals \(X\), \(T\) halts with an encoding of \(F(X)\) on the tape when an encoding of \(X\) is given on the initial tape. A public key encryption scheme is defined as a pair of ITTM-computable functions \(F,G: \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}\) such that there exist real numbers \(p,q\) with \(F(p,G(q,m)) = m\) for all \(m \in \mathbb{R}\). We say that such a \((p,q)\) is a key pair for the scheme \((F,G)\). (For the sake of discussion, \(G\) is an encrypting function, \(F\) is a decrypting function. \(p\) is a private key, and \(q\) is a public key. The second argument of \(G\) and the output of \(F\) are called the plaintext, and the second argument of \(F\) and the output of \(G\) are called the ciphertext.) Given a public key encryption scheme \((F,G)\), a key pair \((p,q)\) is considered secure iff there exists no ITTM-computable function \(H: \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}\) such that for all \(m\), \(H(q,G(q,m)) = m\). (Candidate values of \(H\) are called adversaries.) A public key encryption scheme is secure iff it has a secure key pair. Does there exist a secure public key encryption scheme? Originally proposed by LittlePeng9 on ##googology. If the answer is "yes," then in an ITTM world, people would be able to enjoy complete privacy and construct digital signatures impervious to forgery :) it's vel 09:23, October 26, 2014 (UTC) In simpler terms, can we construct some encoding system, which consists of two functions, G (encoding function) and F (decoding function), and two keys, p (private decryption key) and q (public encryption key), such that we cannot encode decoded message given access to public key and encryption method, but it's possible using private key? LittlePeng9 (talk) 09:27, October 26, 2014 (UTC Well, the answer is "yes", but it's a bit more trivial than I expected: As shown by Hamkins, there exists \(c\in\Bbb R\) which can be recognized by some ITTM \(T\) (which means that \(T\) returns "yes" only for input \(c\), and returns "no" otherwise), but cannot be written by any ITTM. Now we choose \(p=c\) be our private key. Public key isn't even required, we can take it to be empty string. Now we define function \(G\) as follows: for input \(x\), it first checks if \(x=c\). If it's the case, it returns empty output. Otherwise, we return \(1x\) (concatenation of single 1 and input). Now, if adversary existed, it would have to return \(c\) given empty input, which is impossible. But we still can decode message with private key: if we recive empty string, we can just write down \(c\) to which we have access. Otherwise, we just remove first 1 and we get original message. So this coding is safe, at least by our definition. LittlePeng9 (talk) 11:53, October 26, 2014 (UTC) : To make it more reasonable, we may want every adversary to be correct at most countably many times. LittlePeng9 (talk) 13:18, October 26, 2014 (UTC) :: I'm worried that we're just playing Whack-a-Mole here. The absence of probability and computational efficiency seems to be causing such unreasonable situations. it's vel 19:38, October 26, 2014 (UTC) :::There is a reasonable meaning of "probability" for ITTMs, namely coin-flipping measure. Few reasonable notions of "almost all" for sets of infinite binary strings are, for example, having full measure, containing all but countably many elements, being co-meager. LittlePeng9 (talk) 19:45, October 26, 2014 (UTC) So the revised question is now: Does there exist a secure public key encryption scheme such that any plausible adversary is right at most countably many times? LittlePeng9 (talk) 19:48, October 26, 2014 (UTC)